package LinearList;

public class SingleLinkedList { //单链表-火车类
//当前火车中车厢的节点个数（实际就是具体元素的个数）
    private int size;
    //火车头
    private Node head;
    /**
     * 1.在火车头部添加元素-实际就是添加一个车厢节点【头插法】
     * @param val
     */
    public void addFirst(int val){
        Node node=new Node(val);
        //判断当前火车头是否为空
        if(head==null){
            head=node;
        }else{//火车中有节点，要把新车厢挂载到火车头部
            node.next=head;
            head=node;
        }
        size++;//车箱数＋1
    }
    /**
     * 2.在链表的中间位置插入
     * @param index 插入位置的的下标
     * @param val 待插入元素
     */
    public void addIndex(int index,int val){
        //1.合法性2.边界index==0，调用头插3.中间位置插入：找前驱（循环）然后插入
        if(index<0||index>size){
            System.err.println("add index illegal!");
            return;
        }
        if(index==0){
            addFirst(val);
            return;
        }
        Node node=new Node(val);
        Node prev=head;
        for (int i = 0; i < index-1; i++) {
            prev=prev.next;
        }
        node.next=prev.next;
        prev.next=node;
        size++;
    }
    /**
     * 3.查：返回index位置元素
     */
    public int get(int index){
        if (rangeCheck(index)){
            Node node=head;
            for (int i = 0; i < index; i++) {
                node=node.next;
            }
            return node.val;
        }else{
            System.out.println("get index illegal");
            return -1;
        }
    }
    private boolean rangeCheck(int index){
        if(index<0||index>=size){
            return false;
        }
        return true;
    }
    /**
     *4. contains(int value):查询值为value的元素是否在单链表中存在
     */
    public boolean contains(int val){
        for(Node temp=head;temp!=null;temp=temp.next){
            if(temp.val==val){
                return true;
            }
        }
        return false;
    }
    /**
     * 5.改：set(int index,int newValue):修改index位置的值为newVale,返回改前的值
     */
    public int set(int index,int newVal){
        if(rangeCheck(index)){
            Node node=head;
            for (int i = 0; i < index; i++) {
                node=node.next;
            }
            int oldVal=node.val;
            node.val=newVal;
            return oldVal;
        }else{
            System.out.println("set index illegal");
            return -1;//不准确，万一原来的值就是-1呢？
        }
    }
    /**
     * 6.removeIndex(int index);删除链表中index节点
     */
    public void removeIndex(int index){
        if(rangeCheck(index)){
            if(index==0){
                Node temp=head;
                head=head.next;
                temp.next=null;
                size--;
            }else{
                //index不处于头节点处-找前驱
                Node prev=head;
                for (int i = 0; i < index - 1; i++) {
                    prev=prev.next;
                }
                Node cur=prev.next;
                prev.next=cur.next;
                cur.next=null;
                size--;
            }
        }else{
            System.out.println("remove index illegal");
            return;
        }
    }
    public void removeFirst(){
        removeIndex(0);
    }
    public void removeLast(){
        removeIndex(size-1);
    }
    /**
     * 7.removeValueOnce(int val):删除单链表中第一个值为val的节点
     */
    public void removeValOnce(int val){
        //先判断头节点
        if(head.val==val){
            Node node=head;
            head=head.next;
            node.next=null;
            size--;
        }else{
            //head一定不是待删除结点
            Node prev=head;
            while(prev.next!=null){
                if(prev.next.val==val){
                    Node cur=prev.next;
                    prev.next=cur.next;
                    cur.next=null;
                    size--;
                    return;
                }
                prev=prev.next;
            }
        }
    }
    /**
     * 8.removeValueAll(int val):删除单链表中所有值为val的节点
     */
    public void removeValAll(int val){
        //判断头节点
        while(head!=null&&head.val==val){
            head=head.next;
            size--;
        }
        if(head==null){
            return;
        }else{
            //head一定不是待删除结点并且链表中还有节点
            Node prev=head;
            while(prev.next!=null){
                if(prev.next.val==val){
                    prev.next=prev.next.next;
                    size--;
                }else{
                    prev=prev.next;
                }
            }
        }
    }
    /**
     * 遍历单链表-打印出单链表
     * @return返回值String
     */
    public String toString(){
        String ret="";
        //从火车头走到火车尾。遍历过程中需要创建临时变量否则遍历完head为空，火车丢了
        Node node=head;
        while(node!=null){
            ret+=node.val;
            ret+="->";
            node=node.next;//继续访问下一节车厢
        }
        ret+="NULL";
        return ret;
    }
}
class Node{//车厢类，一个车厢只能保存一个元素
    int val;//存储具体数值
    Node next;//下一个车厢的地址
    public Node(int val){//构造方法-用于赋初值
        this.val=val;
    }
}
